function binarySearchTree() {
  let Node = function (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  };
  let root = null;

  //插入节点
  this.insert = function (key) {
    let node = new Node(key);
    if (root === null) {
      root = node;
    } else {
      insertNode(root, node);
    }
  };
  function insertNode(node, newNode) {
    if (newNode.key < node.key) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        insertNode(node.right, newNode);
      }
    }
  }

  //搜索节点
  this.search = function (key) {
    return nodeSearch(root, key);
  };
  function nodeSearch(node, key) {
    if (node.key === key) {
      return true;
    }
    if (key < node.key && node.left != null) {
      nodeSearch(node.left, key);
    } else if (key > node.key && node.right != null) {
      nodeSearch(node.right, key);
    }
    return false;
  }

  /**
   * 遍历
   */

  //中序遍历
  this.inOrderTraverse = function () {
    inOrderTraverseNode(root);
  };
  function inOrderTraverseNode(node) {
    if (node !== null) {
      console.log(node.key);
      inOrderTraverseNode(node.left);
      inOrderTraverseNode(node.right);
    }
  }

  //中序遍历
  this.preOrderTraverse = function () {
    preOrderTraverseNode(root);
  };
  function preOrderTraverseNode(node) {
    if (node !== null) {
      preOrderTraverseNode(node.left);
      console.log(node.key);
      preOrderTraverseNode(node.right);
    }
  }

  //后序遍历
  this.postOrderTraverse = function () {
    postOrderTraverseNode(root);
  };
  function postOrderTraverseNode(node) {
    if (node !== null) {
      postOrderTraverseNode(node.left);
      postOrderTraverseNode(node.right);
      console.log(node.key);
    }
  }

  //层次遍历
  this.layerOrderTraverse = function () {
    layerOrderTraverseNode(root);
  };
  function layerOrderTraverseNode(node) {
    if (node === null) return [];
    let arr = [];
    arr.push(root);
    let res = [];
    while (arr.length) {
      let len = arr.length;
      let tmp = [];
      while (len) {
        let n = arr.shift();
        if (!n) break;
        tmp.push(n.key);
        if (n.left) {
          arr.push(n.left);
        }
        if (n.right) {
          arr.push(n.right);
        }
        len--;
      }
      res.push(tmp);
    }
    console.log(res);
  }

  //删除节点
  this.remove = function (key) {
    root = removeNode(root, key);
  };
  function removeNode(node, key) {
    if (node === null) {
      return null;
    }
    if (key < node.key) {
      node.left = removeNode(node.left, key);
      return node;
    } else if (key > node.key) {
      node.right = removeNode(node.right, key);
      return node;
    } else {
      //是叶子节点
      if (node.left === null && node.right === null) {
        node = null;
        return node;
      }
      if (node.left === null) {
        node = node.right;
        return node;
      } else if (node.right === null) {
        node = node.left;
        return node;
      }
      let n = findMin(node.right);
      node = n;
      removeNode(node.right, n.key);
      return node;
    }
  }

  function findMin(node) {
    if (node) {
      while (node !== null && node.left !== null) {
        node = node.left;
      }
      return node;
    }
    return null;
  }
}

let node1 = new binarySearchTree();
node1.insert(4);
node1.insert(8);
node1.insert(2);
node1.insert(6);
node1.remove(7);
//node1.inOrderTraverse();
node1.layerOrderTraverse();
